DROPS

Document

DOI: 10.4230/LIPIcs.ITC.2020.4

Practical Relativistic Zero-Knowledge for NP

Authors: Claude Crépeau, Arnaud Y. Massenet, Louis Salvail, Lucas Shigeru Stinchcombe, and Nan Yang

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract

In a Multi-Prover environment, how little spatial separation is sufficient to assert the validity of an NP statement in Perfect Zero-Knowledge ? We exhibit a set of two novel Zero-Knowledge protocols for the 3-COLorability problem that use two (local) provers or three (entangled) provers and only require exchanging one edge and two bits with two trits per prover. This greatly improves the ability to prove Zero-Knowledge statements on very short distances with very basic communication gear.

Cite as

Claude Crépeau, Arnaud Y. Massenet, Louis Salvail, Lucas Shigeru Stinchcombe, and Nan Yang. Practical Relativistic Zero-Knowledge for NP. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{crepeau_et_al:LIPIcs.ITC.2020.4,
  author =	{Cr\'{e}peau, Claude and Massenet, Arnaud Y. and Salvail, Louis and Stinchcombe, Lucas Shigeru and Yang, Nan},
  title =	{{Practical Relativistic Zero-Knowledge for NP}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{4:1--4:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.4},
  URN =		{urn:nbn:de:0030-drops-121091},
  doi =		{10.4230/LIPIcs.ITC.2020.4},
  annote =	{Keywords: Multi-Prover Interactive Proofs, Relativistic Commitments, 3-COLorability, Quantum Entanglement, Non-Locality}
}

Document

DOI: 10.4230/LIPIcs.TQC.2017.3

Provably Secure Key Establishment Against Quantum Adversaries

Authors: Aleksandrs Belovs, Gilles Brassard, Peter Høyer, Marc Kaplan, Sophie Laplante, and Louis Salvail

Published in: LIPIcs, Volume 73, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)

Abstract

At Crypto 2011, some of us had proposed a family of cryptographic protocols for key establishment capable of protecting quantum and classical legitimate parties unconditionally against a quantum eavesdropper in the query complexity model. Unfortunately, our security proofs were unsatisfactory from a cryptographically meaningful perspective because they were sound only in a worst-case scenario. Here, we extend our results and prove that for any \eps > 0, there is a classical protocol that allows the legitimate parties to establish a common key after O(N) expected queries to a random oracle, yet any quantum eavesdropper will have a vanishing probability of learning their key after O(N^(1.5-\eps)) queries to the same oracle. The vanishing probability applies to a typical run of the protocol. If we allow the legitimate parties to use a quantum computer as well, their advantage over the quantum eavesdropper becomes arbitrarily close to the quadratic advantage that classical legitimate parties enjoyed over classical eavesdroppers in the seminal 1974 work of Ralph Merkle. Along the way, we develop new tools to give lower bounds on the number of quantum queries required to distinguish two probability distributions. This method in itself could have multiple applications in cryptography. We use it here to study average-case quantum query complexity, for which we develop a new composition theorem of independent interest.

Cite as

Aleksandrs Belovs, Gilles Brassard, Peter Høyer, Marc Kaplan, Sophie Laplante, and Louis Salvail. Provably Secure Key Establishment Against Quantum Adversaries. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{belovs_et_al:LIPIcs.TQC.2017.3,
  author =	{Belovs, Aleksandrs and Brassard, Gilles and H{\o}yer, Peter and Kaplan, Marc and Laplante, Sophie and Salvail, Louis},
  title =	{{Provably Secure Key Establishment Against Quantum Adversaries}},
  booktitle =	{12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)},
  pages =	{3:1--3:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-034-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{73},
  editor =	{Wilde, Mark M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2017.3},
  URN =		{urn:nbn:de:0030-drops-85816},
  doi =		{10.4230/LIPIcs.TQC.2017.3},
  annote =	{Keywords: Merkle puzzles, Key establishment schemes, Quantum cryptography, Adversary method, Average-case analysis}
}

Search Results

Documents authored by Salvail, Louis

Practical Relativistic Zero-Knowledge for NP

Abstract

Cite as

Provably Secure Key Establishment Against Quantum Adversaries

Abstract

Cite as

Thanks for your feedback!

Could not send message